1. Field of the Invention
This invention relates to the art of generating digital representations of alpha-numeric characters or other symbols. More particularly, it relates to the generation of bitmap representations of characters at selectable resolutions and point sizes, from digital representations of their outlines.
2. Discussion of the Prior Art
The field of electronic typographic and image composition has given birth to a large variety of display devices and printing systems for making visible in printed or other form (e.g., on a video display screen) alphanumeric and other characters and symbols. (Hereafter the term "output device" will be used generically, to include all types of print and non-print output devices.) This field includes, but is not limited to, electronic typesetting and publishing systems, full page composition systems, word processing systems, and all of their output devices. In such systems, each character or symbol must be supplied, at some point in the systems, as digital information from which the character form may be constructed on each output device. The digital data will generally have to be compiled or generated in a way which takes into account specific characteristics of the output device, such as its resolution, and specific characteristics of the image to be displayed, such as the point size desired for typographic material.
A large number of typefaces are in popular use. The generation of each character or symbol in each typeface desired, at each point size to be used, can be a substantial undertaking. For a small manufacturer, the cost of developing all of this material could make the effort quite impractical. And when a new output device is developed, with different characteristics, it could be necessary to prepare a new digital data set for characters adapted thereto. This can make it quite expensive to take advantage of improvements in output technology as they become available.
Fortunately, it is not necessary to start "from scratch" each time a character set, font, or symbol is needed. Digital forms of a large number of typefaces and other symbols are available from a number of suppliers. However, these suppliers frequently will not have a digital representation in a form which meets the user's requirements or the characteristics of his output device. The typeface supplier generally wants to establish as its "master" digital version of a character a form which is as close to an analog form as possible--that is, a form which is virtually independent of output device characteristics and the point size at which characters are to be viewed. The most frequently employed approach is to store an encoded representation of the outlines of each of the characters. The location of the outline is defined using a normalized coordinate system whose resolution is considerably finer than the resolution of any conceivable output device for any reasonable selection of point size. Several techniques are available for encoding character outlines. These range from storing every point on the outline to storing closely spaced points which can be connected by straight lines to storing only selected "control points" which define the curves and straight lines of a character according to a known set of rules. The use of outline encoding reduces the amount of memory needed to store a typeface and provides a size-independent character representation. However, most output devices will not accept the encoded-outline character data; they require that characters be represented in a so-called "bitmap" form, as a list of numbers locating the position of each point in the character shape (i.e., not only every point on the outline, but every point in the interior of the character, as well). A translation or transformation is therefore required from the outline form to the bitmap form.
To understand the nature of this transformation, start by considering the display medium as a rectangular grid of N.times.M locations, each location representing a single picture element (or "pixel") which may be turned on (to display a part of a character) or left turned off (to represent background). The state of each picture element can be represented by a single bit whose value is either zero or one (of course, additional bits can be added to represent color, intensity or other attributes). When a character is stored in bitmap form, it is represented in a memory as a bit pattern corresponding to the intended illumination of picture elements on the display. The whole display field is represented in a memory array as an assemblage of bitmap characters.
Smaller-sized characters are made up of fewer pixels than larger characters and have smaller bitmap representations. It is thus necessary to make available for each character which is to be displayable, a separate bitmap representation in each required size. Further, since each bit in the memory corresponds to a selectable pixel location on the display, and pixel locations depend on display resolution, a separate bitmap representation is required for each different resolution output device. Therefore, although the outline representation of a character can be done at a sufficiently high resolution as to be independent of size and display resolution for all practical intents, the bitmap representation is necessarily dependent on the point size to be displayed and the resolution of the output device.
Frequently, important points on the ideal outline locus of a character will fall between the available pixel locations on the display field, requiring that choices be made as to which of the available pixels to use to represent those portions of the outline. And as a character is scaled up or down in size, certain adjustments may have to be made to account for the human visual perception mechanisms which cause the character to be viewed as having specific qualities. For example, as point size is changed, it is often appropriate that the height and width of the character be varied by slightly different scaling factors.
A still further complicating factor is the fact that for typographic consistency, certain characterizing features and relationships between features of different characters must be preserved through the outline-to-bitmap conversion process. For example, the heights of certain portions of specified letters must be kept the same, the widths of certain portions of letters must be maintained in a desired relationship, and so forth. Failure to preserve these relationships will cause loss of the typeface's design identity and typographic quality.
The promotion of the appearance of unity between the characters in a typeface has sometimes been accomplished by using conventional signal processing techniques such as filtering. That approach, however, provides improved uniformity (e.g., in the thickness of lines) only at the expense of diminished resolution. This is a direct consequence of performing operations on character spectra rather than operating on character features.
The conversion of outline representations of typefaces to bitmap representations of selectable point size and resolution has therefore been difficult to achieve with an automatic system, particularly where typographic design integrity is to be maintained in the bitmap product. High quality conversion has required considerable human "polishing" or editing of any bitmap which has been generated from an outline form by an automated system. This manual editing is, of course, expensive and time consuming. Moreover, since editing is required for each point size, a system cannot be provided with an ability to select an arbitrary point size for type. This restricts the user to just those point sizes for which edited type has previously been created.
It is therefore an object of the present invention to provide a system which can more efficiently convert outline representations of individual characters and typefaces to corresponding bitmaps of those characters and typefaces within a wide range of sizes and display resolutions.
A further object of the invention is to provide a system for conversion of character outline data to corresponding bitmap data with only minimal human intervention or involvement, while maintaining a high level of typographic quality.
Still another object of the invention is to provide an efficient mechanism for converting into bitmap form character information stored in outline form.
Yet another object of the invention is to provide a method for converting into bitmap form character information stored in outline form, based on knowledge of the features of characters rather than their spectral properties.